export class TreeNode<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent?: TreeNode<T> | null = null;

  value: T;
  constructor(value: T) {
    this.value = value;
  }

  //是否是左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this);
  }

  //是否是右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this);
  }
}

export class AVLTreeNode<T> extends TreeNode<T> {
  left: AVLTreeNode<T> | null = null;
  right: AVLTreeNode<T> | null = null;
  parent: AVLTreeNode<T> | null = null;

  height: number = 1;

  //获得树的高度，最长的子节点level
  private getHeight(): number {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    return Math.max(leftHeight, rightHeight) + 1;
  }

  //平衡因子左侧高度减去右侧高度
  private getBalanceFactor() {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    return leftHeight - rightHeight;
  }

  //直接判断当前节点是否平衡 平衡因子在【-1，1】区域为正常，其他为不平衡
  public get isBalanced(): boolean {
    return this.getBalanceFactor() >= -1 && this.getBalanceFactor() <= 1;
  }

  //获取更高子节点
  public get higherChild(): AVLTreeNode<T> | null {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    if (leftHeight > rightHeight) return this.left;
    if (leftHeight < rightHeight) return this.right;

    return this.isLeft ? this.left : this.right;
  }
}

// const avl = new AVLTreeNode<number>(5);
// avl.right = new AVLTreeNode<number>(10);
// avl.right.right = new AVLTreeNode<number>(20);

// console.log(avl.higherChild);
